function AStar() {}

AStar.MAZE = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
];

AStar.aStarSearch = function(start, end) {
    var openList = [];
    var closeList = [];
    //把起点加入 openList
    openList.push(start);
    //主循环，每一轮检查一个当前方格节点
    while (openList.length > 0) {
        // 在openList中查找 F值最小的节点作为当前方格节点
        var currentGrid = this._findMinGird(openList);
        // 当前方格节点从openList中移除
        openList.splice(openList.indexOf(currentGrid), 1);
        // 当前方格节点进入 closeList
        closeList.push(currentGrid);
        // 找到所有邻近节点
        var neighbors = this._findNeighbors(currentGrid, openList, closeList);
        for (var i = 0; i < neighbors.length; i++) {
            grid = neighbors[i];
            //邻近节点不在openList中，标记父亲、G、H、F，并放入openList
            grid.initGrid(currentGrid, end);
            openList.push(grid);
        }
        //如果终点在openList中，直接返回终点格子
        for (var i = 0; i < openList.length; i++){
            var grid = openList[i];
            if ((grid.x == end.x) && (grid.y == end.y)) {
                return grid;
            }
        }
    }
    //openList用尽，仍然找不到终点，说明终点不可到达，返回空
    return null;
};

AStar._findMinGird = function(openList) {
    var tempGrid = openList[0];
    for (var i = 0; i < openList.length; i++){
        var grid = openList[i];
        if (grid.f < tempGrid.f) {
            tempGrid = grid;
        }
    }
    return tempGrid;
};

AStar._findNeighbors = function(grid, openList, closeList) {
    var gridList = [];
    if (this._isValidGrid(grid.x, grid.y-1, openList, closeList)) {
        gridList.push(new Grid(grid.x, grid.y - 1));
    }
    if (this._isValidGrid(grid.x, grid.y+1, openList, closeList)) {
        gridList.push(new Grid(grid.x, grid.y + 1));
    }
    if (this._isValidGrid(grid.x-1, grid.y, openList, closeList)) {
        gridList.push(new Grid(grid.x - 1, grid.y));
    }
    if (this._isValidGrid(grid.x+1, grid.y, openList, closeList)) {
        gridList.push(new Grid(grid.x + 1, grid.y));
    }
    return gridList;
};

AStar._isValidGrid = function(x, y, openList, closeList) {
    //是否超过边界
    if (x < 0 || x >= this.MAZE.length || y < 0 || y >= this.MAZE[0].length) {
        return false;
    }
    //是否有障碍物
    if(this.MAZE[x][y] == 1){
        return false;
    }
    //是否已经在openList中
    if(this._containGrid(openList, x, y)){
        return false;
    }
    //是否已经在closeList中
    if(this._containGrid(closeList, x, y)){
        return false;
    }
    return true;
};

AStar._containGrid = function(grids, x, y) {
    for (var i = 0; i < grids.length; i++) {
        var grid = grids[i];
        if ((grid.x == x) && (grid.y == y)) {
            return true;
        }
    }
    return false;
};

function Grid(x, y) {
    this.x = x;
    this.y = y;
    this.f = 0;
    this.g = 0;
    this.h = 0;
    this.parent = null;
    
    this.initGrid = function(parent, end){
        this.parent = parent;
        this.g = parent.g + 1;
        this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
        this.f = this.g + this.h;
    }
}

//设置起点和终点
var startGrid = new Grid(2, 1);
var endGrid = new Grid(2, 5);
//搜索迷宫终点
var resultGrid = AStar.aStarSearch(startGrid, endGrid);
//回溯迷宫路径
var path = [];
while (resultGrid != null) {
    path.push(new Grid(resultGrid.x, resultGrid.y));
    resultGrid = resultGrid.parent;
}
//输出迷宫和路径，路径用星号表示
for (var i = 0; i < AStar.MAZE.length; i++) {
    var line = '';
    for (var j = 0; j < AStar.MAZE[0].length; j++) {
        if (AStar._containGrid(path, i, j)) {
            line += ("*, ");
        } else {
            line += (AStar.MAZE[i][j] + ", ");
        }
    }
    console.log(line);
}